%0 Conference Proceedings
%4 sid.inpe.br/mtc-m21b/2016/10.05.17.47
%2 sid.inpe.br/mtc-m21b/2016/10.05.17.47.45
%T Aplicação da metaheurística BRKGA com heurística de busca local para o problema de agrupamento com restrições
%D 2016
%A Oliveira, Rudinei Martins,
%A Chaves, Antonio Augusto,
%A Lorena, Luiz Antonio Nogueira,
%@affiliation Universidade Federal de São Paulo (UNIFESP)
%@affiliation Universidade Federal de São Paulo (UNIFESP)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@electronicmailaddress rudmart@gmail.com
%@electronicmailaddress antonio.chaves@unifesp.br
%@electronicmailaddress luiz.lorena@inpe.br
%B Simpósio Brasileiro de Pesquisa Operacional, 48 (SBPO)
%C Vitória, ES
%8 27-30 set.
%S Anais
%K BRKGA, busca local, problema de agrupamentos, heurística, restrições BRKGA, Local Search, Clustering Problem, Heuristic, Constraints.
%X Este artigo propõe um método híbrido que combina o BRKGA com uma heurística de busca local para resolver o problema de agrupamentos com restrições. O problema de agrupamentos consiste em separar um conjunto de objetos em grupos tal que os membros de cada grupo sejam similares entre si. No problema de agrupamentos com restrições, alguns objetos são definidos a priori para estar no mesmo grupo (restrições must-link) ou em grupos distintos (restrições cannotlink). Este problema é classificado como NP-hard. O BRKGA e uma recente metaheurística que codifica uma solução como um vetor de chaves aleatórias e produz uma solução viável através de um algoritmo determinista. Os resultados computacionais considerando dados reais disponíveis na literatura são comparados com uma abordagem de geração de colunas. ABSTRACT: This paper proposes a hybrid method that combines the BRKGA with a local search heuristic to solve the clustering problem with constraints. The clustering problem consists in separating a set of objects into groups such that members of each group are similar to each other. In the clustering problem with constraints, some objects are defined, a priori, to be in the same group (must-link constraints) or in distinct groups (cannot-link constraints). This problem is well known to be NP-hard. The BRKGA is a recent metaheuristic that encodes a solution as a vector of random keys and produces a feasible solution through a deterministic algorithm. Computational results considering real data available in the literature are compared with a column generation approach.
%3 Oliveira_aplicacao.pdf